/* 输出无向图点u到点v的所有路径 */

#include <iostream>
#include "algraph.h"
using namespace std;

// 输出路径
void findpath(ALGraph *G, int u, int v, int path[], int d, int visit[])
{
  
  int w, i;
  
  // 将结点加载进路径
  path[++d] = u;
  
  // 更新访问信息
  visit[u] = 1;
  
  // 如果u、v为同一结点，输出路径
  if (u == v)
  {
    cout << endl;
    for (int i = 0; i <= d; ++i)
      cout << path[i] << " ";
  }
  
  // 找到邻接结点
  ArcNode *p = G->adjlist[u].firstarc;
  
  // 邻接结点不为空
  while (p != NULL)
  {
    // 邻接结点的序号
    w = p->adjvex;
    
    // 邻接结点未被访问
    if (visit[w] == 0)
      findpath(G, w, v, path, d, visit); // 找邻接结点到v结点的路径
    
    // 到下一个邻接结点
    p = p->nextarc;
  }
  
  // 更新访问信息
  visit[u] = 0;
}

int main()
{
  // 创建图 -- 邻接表
  ALGraph *G = create_algraph(4, 5);
  
  // 访问标记，初始时结点均未被访问
  int visit[maxsize];
  for (int i = 0; i < G->numver; ++i)
    visit[i] = 0;
  
  // 记录路径
  int path[maxsize];
  
  // 输出0号结点到3号结点的所有路径
  findpath(G, 0, 3, path, -1, visit);
  return 0;
}